/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * MaxHeap.java
 * ---------------------------
 *
 */
package heaps;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Implementation of Min/Max heap as found in "Introduction to Algorithms
 * (Cormen et al.)", with the difference that for easyness an ArrayList is used,
 * together with a custom comparator.
 * <p>
 * Note: for all operations, keep in mind that the array is zero-based, so the
 * children are: 2n+1 and 2n+2, and the parent is (n-1)/2 (automatically
 * floored).
 * <p>
 * Note that it's impossible to usefully implement the generic version of this
 * class due to static methods (thanks to f**** Java).
 */
@SuppressWarnings("unchecked")
public abstract class Heap <T>
{
	private final List<T> _values;

	/** Change to public and anonymously override isTop() for a custom Heap */
	protected Heap()
	{
		_values = new ArrayList<T>();
	}
	
	public static Heap createMaxHeap()
	{
		return new Heap() 
		{
			@Override
			protected boolean isTop(Object val0, Object val1) {
				return ((Comparable)val0).compareTo(val1) > 0;
			}
		};
	}
	
	public static Heap createMinHeap()
	{
		return new Heap() 
		{
			@Override
			protected boolean isTop(Object val0, Object val1) {
				return ((Comparable)val0).compareTo(val1) < 0;
			}
		};
	}
	
	public void insert(T value)
	{
		if (value == null) throw new NullPointerException("No null values accepted");
		
		_values.add(value);
		bubble(value, _values.size() - 1);
	}

	/**
	 * @return null if no values in the heap.
	 */
	public T top()
	{
		if (_values.size() == 0) return null;
		
		return _values.get(0);
	}
	
	/**
	 * @return null if no values in the heap.
	 */
	public T extractTop()
	{
		if (_values.size() == 0) return null;
		
		T max = _values.remove(0);
		
		if (_values.size() > 0) {
			Collections.rotate(_values, 1); // move the last to the top :-)))
			heapify(0);
		}
		
		return max;
	}

	/**
	 * "Top up" the key, which is: increase in case of max heap, decrease in case
	 * of min heap; the opposite operations are not allowed.<br>
	 */
	public void topUpKey(int pos, T value)
	{
		T oldValue = _values.get(pos);
		if (! isTop(value, oldValue)) throw new IllegalArgumentException("Not topping up!");
		
		_values.set(pos, value);
		bubble(value, pos);
	}
	
	public int size()
	{
		return _values.size();
	}
	
	private void heapify(int pos) 
	{
		int largestPos = pos;
		T value = _values.get(pos);
		
		// is the left the largest?
		int leftPos = 2 * pos + 1;
		boolean hasLeft = leftPos < _values.size();
		
		if (hasLeft) {
			T left = _values.get(leftPos);

			if (isTop(left, value)) {
				largestPos = leftPos;
			}
		}
		
		// is the right the largest?
		int rightPos = 2 * pos + 2;
		boolean hasRight = rightPos < _values.size();
		
		if (hasRight) {
			T right = _values.get(rightPos);
			T largest = _values.get(largestPos); 

			if (isTop(right, largest)) {
				largestPos = rightPos;
			}
		}

		// did we found a largest?
		if (largestPos != pos) {
			swap(largestPos, pos);
			heapify(largestPos); // not largest anymore
		}
	}

	private void bubble(T value, int pos)
	{
		// while has a parent
		while (pos > 0) {
			int parentPos = ((pos - 1) / 2);
			T parent = _values.get(parentPos);
			
			// stop when parent is bigger
			if (isTop(parent, value)) break;
			
			swap(pos, parentPos);
			pos = parentPos;
		}
	}

	private void swap(int pos1, int pos2)
	{
		T value1 = _values.get(pos1);
		T value2 = _values.get(pos2);

		_values.set(pos1, value2);
		_values.set(pos2, value1);
	}
	
	@Override
	public String toString()
	{
		return _values.toString();
	}
	
	protected abstract boolean isTop(T val0, T val1); 
}